package Lecture9;

import java.util.Arrays;

import urok6.prob11;

public class SortHeap {

	public static void main(String[] args) 
	{
		int[] array = {901,882,453,654,5555,86,7,18,109,300};

		//int[] array = { 55,8,6,34,7,51,17,25,44,13};
		//int[] array = { 4,8,7,1,4,8,4,7};
		//int[] array = { 9,5,4,8,6,7,0,1};
		System.out.println(Arrays.toString(array));
		
		array = buildHeap(array);
		System.out.println(Arrays.toString(array));
		
		array = SortHeap(array);
		System.out.println( Arrays.toString(array));
	}
	
	public static int[] buildHeap(int[] array)
	{
		
		for( int i = 0; i < array.length; i++)
		{
			int nodeIndex = i;
			
			while( nodeIndex != 0)
			{
				int parentIndex = (nodeIndex-1) / 2;
				
				if (array[nodeIndex] > array[parentIndex])
				{
					int temp = array[nodeIndex];
					array[nodeIndex] = array[parentIndex];
					array[parentIndex] = temp;
					
				}
				nodeIndex = parentIndex;
			}
		}
		
		
		
		
		
		return array;
	}
	
	public static int[] SortHeap(int[] array)
	{
		array = buildHeap(array);
		
		for( int i = 0; i < array.length; i++)
		{
			swap(array, 0 , array.length-1-i);
			
			int heapLength = array.length-1-i;
			int parentIndex = 0;
			
			while(true)
			{
			int leftChildIndex = parentIndex*2+1; 
			int rightChildIndex = parentIndex*2+2;
			
			if(leftChildIndex >= heapLength)		              // no child at all
			{
				break;
			}
			else
				if(rightChildIndex >= heapLength)                     //only left child
			{
				if(array[leftChildIndex] > array[parentIndex])    //if left child > parent
				{
					swap(array, leftChildIndex, parentIndex);
				}
				break;
			}	
			
			else
			{                                                 // have two child's
				if(array[leftChildIndex] > array[rightChildIndex])     // left child bigger than right child
				{
					if(array[leftChildIndex] > array[parentIndex])     // left child bigger then parent 
					{
						swap(array, leftChildIndex, parentIndex);
					}
					parentIndex = leftChildIndex;
				}
				else
				{
					if(array[rightChildIndex] > array[parentIndex])
					{
						swap(array, rightChildIndex, parentIndex);
					}
					parentIndex = rightChildIndex;
				}
					
			
			}
				
			}
			
		}
		
		return array;
	}

	private static void swap(int[] array, int i, int j)
	{
		int t = array[i];
		array[i] = array[j];
		array[j] = t;
		
	}





	
}
